Tulipa mieleeni, että voisi olla näppärää olla työkalu, jolla voisi ottaa kuvan go-laudasta pelin jälkeen ja saada pelin lopputulos automaattisesti laskematta pisteitä itse. Kävi ilmi, että tähän on olemassa jotain ratkaisuja valmiiksi, esimerkiksi muutaman euron hintainen iOS-sovellus, mutta tämä tuntui myös hauskalta omalta ohjelmointiprojektilta.
Nopeasti toimiva ratkaisu
Keksin aika nopeasti idean, miten tätä voisi lähteä toteuttamaan ja alle tunnin koodailulla olikin kasassa jonkinlainen todistus siitä, että tämä on tehtävissä: tiukkaan rajatusta pelilaudan kuvasta sain tunnistettua suurimman osan kivistä oikein.
Tehtävässähän on konenäköpulmaksi paljon tilannetta yksinkertaistavia tekijöitä. Lauta on säännönmukaisen muotoinen ja kivet ladottu laudalle suhtkoht tarkasti. Mustat ja valkoiset kivet erottaa toisistaan helposti ja ruskean pelilaudankin luulisi erottuvan kivistä melko hyvin. Ensimmäinen ajatukseni olikin jakaa kuva 19×19-ruudukoksi, ottaa jokaisen ruudun keskeltä näytepala ja tutkailla tämän näytepalan värien kirkkautta. Jos ruutu on hyvin kirkas, se on valkoinen kivi; jos ruutu on hyvin tumma, se on musta kivi. Pelilauta on sitten siinä välissä.
Laudan reunojen tunnistaminen
Tämä ei sitten ollut lopullinen toteutustapa, mutta osoittautui sen verran toimivaksi, että siirryin eteenpäin. Seuraava ja vaikeusasteeltaan hieman vaikeampi pulma oli sitten laajentaa kuvaa: entä jos pelilautaa ei olekaan rajattu tiukasti? Kuinka se tunnistetaan kuvasta? Tässäkin kohdassa on helpottavia tekijöitä. Lauta on suorakulmainen, eikä siinä ole tavallisesti kauheasti hukkatilaa reunoilla. Jos löytää reunat, saa suoraan sopivan tiukan rajauksen.
ChatGPT tarjoili vinkkejä reunojen löytämiseen ja suositteli OpenCV-kirjastoa. Sieltä löytyisi Hough transform -tekniikat, joilla reunojen löytäminen olisi helppoa. Päätin kuitenkin tyytyä PHP:n sisäänrakennettuun ja huomattavasti vaatimattomampaan GD-kirjastoon, koska halusin lopputuloksesta sellaisen, että voin tuupata sen mille tahansa webbipalvelimelle (PHP:ta käytän, koska olen työkseni WordPress-kehittäjä ja PHP on siksi koodipuolella äidinkieleni).
Laudan reunojen tunnistus GD:n työkaluilla ei ollut kuitenkaan kovin vaikeaa. ChatGPT neuvoi Sobel-operaattorin pariin. Se on reunankorostustyökalu, joka muuttaa kuvan mustaksi ja piirtää sitten valkoisella kuvaan reunat eli kohdat, joissa väri muuttuu jyrkästi. Tätä versiota kuvasta voidaan sitten tutkia ja etsiä siitä pysty- ja vaakasuoria viivoja. Niitä on paljon, koska go-laudassa on piirrettynä ruudukko, mutta kuvasta etsitään laitimmaiset. Ne ovat laudan reunat (jos kuvassa ei ole mitään kovin suorakulmaista aivan laudan vieressä).
Sobel-operaattori on muuten prosessin hitain vaihe. Omalla koneellani koko prosessin ajaminen vie noin puoli minuuttia, josta melkein koko aika menee Sobel-operaattorin parissa. Onneksi testivaiheessa saattoi aloittaa valmiksi sobeloidusta kuvasta, jolloin prosessin ajoi kolmessa sekunnissa.
Sataprosenttinen varmuus kivien tunnistamiseen
Koska kivien värien tunnistamisessa ja valkoisten kivien ja kirkkaimpien laudan osien erottelemisessa oli vielä ongelmia, sitä puolta piti hioa. Osa ongelmaa on siinä, että vaikka laudan ruudutus ja ruudun keskiosan tutkiminen osuukin käytännössä aina kiven sisään, se voi osua valkoisen kiven varjopuolelle. Laudan osalta luotin laudan mustiin viivoihin, mutta jos analysoitava ruutu on liian pieni ja lauta vähän vinossa, mustat viivat eivät välttämättä osu ruutuun.
Onneksi keksin tähän paremman ratkaisun. Se hyödyntää reunoja korostavaa kuvaa, jossa kivet erottuvat selvästi ympyröinä. Jos tarkastellaan värillisen kuvan sijasta tätä kuvaa, laudan pisteestä erottaa sataprosenttisen varmasti onko siinä kivi vai ei. Jos näyteruudussa on lähes mustaa, se on kivi. Tyhjän pisteen näyteruudun kirkkaus on selvästi korkeampi, koska sitä halkovat valkoiset viivat. Sitten kun tiedetään, missä kaikkialla on kiviä, mustien ja valkoisten kivien erottelu toisistaan on hyvin yksinkertaista.
Elävä vai kuollut?
Nyt kun laudan kokoonpano oli selvillä, ongelmaksi tuli selvittää lopputilanne. Mitkä osat pelilaudasta ovat mustan ja mitkä valkoisen aluetta? Onko laudalla kenties kuolleita kiviä? Asiaa helpottaisi, jos odottaisi, että pelaajat poistavat kaikki kuolleet kivet laudalta. Silloin voisi katsoa, minkäväriset kivet mitäkin aluetta ympäröivät. Tämä olisi helppoa, jos pelaajat vain ovat ympäröineet alueet loppuun asti.
Halusin kuitenkin, että työkalu selviäisi tavallisesta tilanteesta, jossa laudalla on jonkin verran kuolleita kiviä. Samalla hyväksyn, että sataprosenttisen varmasti työkalu ei toimi, koska en halunnut lähteä koodaamaan tarkkaa algoritmia siitä, elävätkö kivet vai eivät – sen täydellinen toteutus menisi luultavasti minun ymmärrykseni yli. Bensonin algoritmista voisi olla apua.
Päädyin yksinkertaisempaan algoritmiin:
- Poistetaan laudalta kaikki ryhmät, joilla on vain yksi vapaus.
- Merkitään kaikki alue, jota ympäröivät vain yhden värin kivet.
- Käydään läpi kaikki tyhjät alueet ja merkitään ne sen pelaajan alueeksi, jonka kiviä alueen ympärillä on enemmän. Ohitetaan kuitenkin pienimmät alueet, koska ne voivat olla dameja eli neutraaleja alueita.
- Jos jollain kivellä on vieressään sekä valkoista että mustaa aluetta, muutetaan pienempi alue isomman väriseksi.
- Poistetaan laudalta kaikki ryhmät, joilla ei ole omanväristä aluetta naapurissa.
- Lopuksi vielä toistetaan vaihe 2.
Algoritmin kehittelyssä oli paljon vaiheita, eikä tätä lopullista muotoa ole testattu kuin yhdellä oikealla pelillä. Voi olla, että hienosäätölekaa tarvitaan vielä. Toisaalta tämän ei tarvitse olla täydellinen: jos joku tilanne on algoritmille liian hankala, pelaajat voivat poistaa hankalimmat kuolleet kivet laudalta.
Paketointi
Lopuksi piti vain rakennella lomake, jolla kuvan voi lähettää ja käsitellä vastaanotettu kuva turvallisesti ettei palvelimelle pysty ujuttamaan ilkeitä skriptejä kuvan sijasta. Ulkoasua piti hioa hieman, jotta työkalu näyttää nätiltä puhelimella, jolla sitä pääasiassa on tarkoitus käyttää. Palvelimella laskenta toimii onneksi nopeammin kuin omalla koneella: tuloksia tulee noin kymmenessä sekunnissa.
Testata saa: palvelu löytyy täältä. Kuvia säilytetään palvelimella määrittelemättömän ajan ja saatan käyttää niitä kehitystarpeisiin. Pisteenlasku on japanilaisittain, kuten Suomessa on tapana, mutta sekit eivät ehkä mene oikein.